package my.study.java.basic.algorithm.sorts;

import java.util.Random;

/**
 * 
 * 堆排序是一种原地（in place）排序算法，二叉堆有两种：最大堆和最小堆
 * Min_Heapify过程：保持最大堆性质的关键，父结点大于等于子节点, 运行时间： O(lgN)
 * Bulid_Min_Heap过程：遍历整个数组，调用Max_Heapify过程，保持所有元素的最大堆性质，
 * 构建最大堆，运行时间：O(n)
 * Heap_Sort过程：遍历整个数组，交换首位元素，并提取首元素，调用Max_Heapify过程，
 * 保持所有元素的最大堆性质，对数组进行原地排序，运行时间：O(nlgn)
 * 
 * @author fanhongjie
 * 
 */
public class HeapSort {
	private static final int N = 10;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Element array[] = new Element[N];
		//int a[] = {14,6,14,14,17,8,8,14,7,16};
		Random random = new Random();
		for (int i = 0; i < N; i++) {
			array[i] = new Element(random.nextInt(2 * N));
			//array[i] = new Element(a[i]);
		}
		System.out.print("Init:\t");
		for (int i = 0; i < N; i++) {
			System.out.print(array[i].getValue() + ",");
		}
		System.out.println();
	}
	private static void HeapSort() {
		
	}
	private static void Bulid_Min_Heap() {
		
	}

}
